package LintCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @Classname Subsets
 * @Description TODO
 * @Date 2021/3/4 11:04
 * @Created by ASUS
 */
public class Subsets {
    /**
     * @param nums: A set of numbers
     * @return: A list of lists
     */
    public List<List<Integer>> subsets(int[] nums) {
        // write your code here
        List<List<Integer>> aList = new ArrayList<>();
        aList.add(new ArrayList<>());
        for (int num : nums) {
            int size = aList.size();
            for (int i = 0; i < size; i++) {
                List<Integer> temp = new ArrayList<>(aList.get(i));
                temp.add(num);
                Collections.sort(temp);
                aList.add(temp);
            }
        }
        return aList;
    }

    public List<List<Integer>> subsets_(int[] nums) {
        // write your code here
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < (1 << nums.length); i++) {
            List<Integer> list = new ArrayList<>();
            int temp = i;
            for (int j = 0; j <= nums.length; j++) {
                if ((temp & 1) == 1) {
                    list.add(nums[j]);
                }
                temp = temp >> 1;// ? what this code mean ?
            }
            result.add(list);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new Subsets().subsets(new int[]{1, 2, 3}));
    }
}
